
/*
 * basic operation:
 * empty(): if the queue is empty than return true
 * pop()  :	delete the element at the top of the heap
 * push(a):	add an element
 * size() : return the elements of the queue
 * top()  : return the element at the top of the heap
 */

#if 0
/* priority queue process linear array */
#include<iosteam>
#include<queue>
#include<algorithm>
#include<vector>

using namespace std;

priority_queue<int> q;

int main()
{
	int i,j,n,x;
	while(cin>>n)
	{
		for(i=0;i<n;i++)
		{
			cin>>x;
			q.push(x);
		}

		while( !q.empty() )
		{
			cout<<q.top()<<" ";
			q.pop();
		}
		cout<<endl;
	}
	return 0 ;
}
#endif


#if 0
/* priority queue process 2D array */
#include<iostream>
#include<queue>
#include<algorithm>
#include<vector>

using namespace std;

struct node
{
	int x,y;
	friend bool operator < (node a,node b)
	{
		return a.x > b.x; //if x is smaller , the priority is larger.
	}
};

priority_queue<node> q;

int main()
{
	int i , j , k,n;
	node a;
	while(cin>>n)
	{
		for(i=0;i<n;i++)
		{
			cin>>a.x>>a.y;
			q.push(a);
		}
		while(!q.empty())
		{
			cout<<q.top().x<<" "<<q.top().y<<endl;
			q.pop();
		}
	}
	return 0;
}

#endif



#if 0
/* priority queue process class */
#include<iostream>
#include<queue>
#include<algorithm>
#include<vector>

using namespace std;

class Edge
{
public:
		int start,end;
		double weight;
		Edge() {}
		Edge(int start , int end , double weight)
		{
			this->start = start;
			this->end = end;
			this->weight = weight;
		}
};

struct ComEdge
{
	bool operator() ( Edge a , Edge b )
	{
		a.weight > b.weight;
	}

};

bool operator>(Edge a ,Edge b)
{
	return a.weight>b.weight;
}

int main()
{
	priority_queue< Edge,vector<Edge>,greater<Edge> > pqueue_Edge;
	pqueue_Edge.push( Edge(0,1,3) );
	pqueue_Edge.push( Edge(0,2,4) );
	pqueue_Edge.push( Edge(0,3,8) );
	pqueue_Edge.push( Edge(0,4,5) );

	while(!(pqueue_Edge.empty()))
	{
		Edge temp = pqueue_Edge.top();
		cout<<"start = "<<temp.start<<" end = "<<temp.end<<" weight =  "<<temp.weight<<endl;
		pqueue_Edge.pop();
	}
	return 0;
}

#endif



/*
 * use the priority_queue to implement the huffman tree
 */

#include<iostream>
#include<stdio.h>
#include<queue>
#include<algorithm>
using namespace std;

class Node
{
public:
		int weight;
		Node* left;
		Node* right;
		Node(int w , Node* l , Node* r) : weight(w) , left(l) , right(r){}
		Node(int w) : weight(w),left(NULL),right(NULL) {}
};


/* traverse in order */
void InOrder(Node *p)
{
	if(p!=NULL)
	{
		InOrder(p->left);
		cout<<p->weight<<"\t";
		InOrder(p->right);
	}
}


/* destroy the binary tree */
void freeTree(Node* p)
{
	if(p->left!=NULL)
	{
		freeTree(p->left);
	}
	if(p->right!=NULL)
	{
		freeTree(p->right);
	}
	delete(p);
}

class cmp
{
public:
	bool operator()(Node* a , Node* b)
	{
		return 	a->weight >= b->weight;
	}
};

int main()
{
	priority_queue< Node* , vector<Node*> , cmp  > q;

	cout<<"The original order : "<<endl;	
	for(int  i=0;i<6;i++)
	{
		Node* temp;
		temp = new Node(rand()%100);
		q.push(temp);
		cout<<temp->weight<<"\t";
	}
	cout<<endl;

	Node* child1;
	Node* child2;
	int w;
	for(int i=1;i<6;i++)
	{
		child1 = q.top();
		q.pop();
		child2 = q.top();
		q.pop();
		w = child1->weight + child2->weight;
		Node* temp;
		temp = new Node(w, child1,child2);
		q.push(temp);
	}

	Node *root = q.top();
	cout<<"Traverse the huffman tree : "<<endl;
	InOrder(root);
	cout<<endl;
	freeTree(root);
	system("pause") ;
	return 0;
}










